package acm.pta13;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.*;
import java.util.function.Function;

// dj+反向边+暴力枚举+树状数组求区间最小值（有点难度）

/**
 * ac代码
 * 思路：
 * 1.枚举从起点到所有点的最短money路径
 * 2.枚举从终点到所有点的最短coin路径
 * 尝试从每个点作为中转点，到达该点后兑换货币，再从该点到终点。记录下每个点的现金值，取最小值
 */
public class 森森旅游2 {
    static Node[] nodes;
    static long[] moneys;
    static long[] coins;
    static int n;
    static int m;
    static int k;
    static final Function<Edge, Integer> byMoney = edge -> edge.money;
    static final Function<Edge, Integer> byCoin = edge -> edge.coin;
    static final Function<Node, List<Edge>> forward = node -> node.nexts;
    static final Function<Node, List<Edge>> backwards = node -> node.pres;

    public static void main(String[] args) {
        Reader sc = new Reader();
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();
        nodes = new Node[n + 1];
        for (int i = 1; i <= n; i++) {
            nodes[i] = new Node(i);
        }
        for (int i = 0; i < m; i++) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            int money = sc.nextInt();
            int coin = sc.nextInt();
            nodes[from].nexts.add(new Edge(nodes[from], nodes[to], money, coin));   //正向边
            nodes[to].pres.add(new Edge(nodes[to], nodes[from], money, coin));  //反向边
        }
        for (int i = 1; i <= n; i++) {
            nodes[i].cash = sc.nextInt();
        }
        moneys = dijkstra(1, forward, byMoney);
        coins = dijkstra(n, backwards, byCoin);
        SegmentTree segmentTree = new SegmentTree();
//        long[] info = select(moneys, coins);
        for (int i = 0; i < k; i++) {
            int index = sc.nextInt();
            nodes[index].cash = sc.nextInt();
            segmentTree.update(1, 1, nodes.length - 1, index);
            System.out.println(segmentTree.tree[1]);
        }
    }

    /**
     * 4 3 1
     * 1 2 1 1
     * 1 3 5 5
     * 3 1 10 10
     * 2 100 1 1
     */
    static class SegmentTree {
        private int N;
        public long[] tree;  //存储每个区间的最小值

        public SegmentTree() {
            N = moneys.length - 1;
            int lenS = (int) Math.pow(2, Math.ceil(Math.log(N) / Math.log(2) + 1));
            this.tree = new long[lenS];
            Arrays.fill(tree, Long.MAX_VALUE);
            build(1, 1, N);
        }

        private void build(int i, int l, int r) {
            if (l == r) {
                if (moneys[l] != Long.MAX_VALUE && coins[l] != Long.MAX_VALUE) {
                    tree[i] = moneys[l] + (long) Math.ceil(1.0 * coins[l] / nodes[l].cash);
                }
                return;
            }
            int mid = (l + r) >> 1;
            build(i << 1, l, mid);
            build(i << 1 | 1, mid + 1, r);
            pushUp(i);
        }

        private void pushUp(int i) {
            tree[i] = Math.min(tree[i << 1], tree[i << 1 | 1]);
        }

        /**
         * 更新x位置的值
         * 从l-r区间开始下放任务，t是l-r对应的位置
         */
        public void update(int i, int l, int r, int x) {
            if (l == r) {
                if (moneys[l] != Long.MAX_VALUE && coins[l] != Long.MAX_VALUE) {
                    tree[i] = moneys[l] + (long) Math.ceil(1.0 * coins[l] / nodes[l].cash);
                }
                return;
            }
            int mid = (l + r) >> 1;
            if (x <= mid)    //x越过左孩子的右边界
                update(i << 1, l, mid, x);
            else
                update(i << 1 | 1, mid + 1, r, x);
            pushUp(i);
        }

        public long query(int i, int l, int r, int L, int R) {
            if (L <= l && R >= r) {    // 如果查询的区间包含了当前节点的区间，就返回当前节点的值
                return tree[i];
            }
            int mid = (l + r) >> 1;  // 计算中间值
            long min = Long.MAX_VALUE;  // 初始化最小值为最大值
            if (L <= mid)  // 如果查询的区间包含了左子树，就在左子树中查询
                min = Math.min(min, query(i << 1, l, mid, L, R));
            if (R > mid)  // 如果查询的区间包含了右子树，就在右子树中查询
                min = Math.min(min, query(i << 1 | 1, mid + 1, r, L, R));
            return min;  // 返回查询结果
        }
    }


    /**
     * 从起点到每个点的最短money路径
     *
     * @param s
     * @param direction 选择正向或者反向
     * @param by        选择money或者coin获取最短路径
     * @return
     */
    public static long[] dijkstra(int s, Function<Node, List<Edge>> direction, Function<Edge, Integer> by) {
        long[] info = {s, 0}; //当前点信息,0:id,1:所需money
        long[] res = new long[n + 1];    //记录每个点的最短money路径
        Arrays.fill(res, Long.MAX_VALUE);
        boolean[] vis = new boolean[nodes.length];
        //根据money升序
        PriorityQueue<long[]> queue = new PriorityQueue<>(Comparator.comparingLong(o -> o[1]));
        int count = 0;    //记录已访问点数
        queue.add(info);
        while (count < n && !queue.isEmpty()) {
            info = queue.poll();
            int id = (int) info[0];
            if (vis[id]) continue;
            res[id] = info[1];
            vis[id] = true;
            count++;
            Node curr = nodes[id];
            for (Edge edge : direction.apply(curr)) {
                Node to = edge.to;
                long newPath = info[1] + by.apply(edge);
                if (vis[to.id] || newPath >= res[to.id]) continue;    //被访问过或者超过最短money路径直接跳过
                res[to.id] = newPath;
                queue.add(new long[]{to.id, newPath});
            }
        }
        return res;
    }


    static class Node {
        int id;
        int cash;   //汇率
        List<Edge> nexts = new LinkedList<>();  //出边
        List<Edge> pres = new LinkedList<>();   //入边

        public Node(int id) {
            this.id = id;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "id=" + id +
                    ", cash=" + cash +
                    '}';
        }
    }

    static class Edge {
        Node from;
        Node to;
        int money;  //所需现金
        int coin;   //所需货币

        public Edge(Node from, Node to, int money, int coin) {
            this.from = from;
            this.to = to;
            this.money = money;
            this.coin = coin;
        }

        @Override
        public String toString() {
            return from.id + "->" + to.id + " " + money + " " + coin;
        }
    }

    static class Reader {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

        public int nextInt() {
            try {
                in.nextToken();
            } catch (Exception ignored) {}
            return (int) in.nval;
        }
    }
}
